package com.algorithm.sort;

/*
希尔排序
排序原理：
1.选定一个增长量h,按照增长量作为数据分组的依据，对数据进行分组；
2.对分好组的每一组数据完成插入排序；
3.减小增长量，最小减为1，重复第二步操作。
 */
public class Shell {
    //希尔排序
    public static void sort(Comparable[] a) {
        //1.根据数组a的长度·确定增长量引的初始值：
        int h = 1;
        while (h < a.length / 2) {
            h = h * 2 + 1;
        }
        //2.希尔排序
        while (h >= 1) {
            //排序
            //找到插入的元素
            for (int i = h; i < a.length; i++) {
                //把待插入的元素插入到有序数列中
                for (int j = i; j >= h; j = j - h) {
                    if (greater(a[j - h], a[j])) {
                        exch(a, j, j - h);
                    } else {
                        break;
                    }
                }
            }
            //减小h的值
            h = h / 2;
        }

    }

    private static boolean greater(Comparable v, Comparable w) {
        return v.compareTo(w) > 0;
    }

    private static void exch(Object[] a, int i, int j) {
        Object t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
